package com.gxc.integer;

public class UniquePathsWithObstacles {

    public static void main(String[] args) {
        /*System.out.println(handle(new int[][]{
                {0,0,0},{0,1,0},{0,0,0}
        }));*/
        System.out.println(handle2(new int[][]{
                {0,0,0},{0,1,0},{0,0,0}
        }));

        /*System.out.println(handle(new int[][]{
                {0,1},{0,0}
        }));*/
        System.out.println(handle2(new int[][]{
                {0,1},{0,0}
        }));
        //System.out.println(2 & ~0);
    }

    public static int handle(int[][] obstacleGrid) {
        if (obstacleGrid[0][0] == 1) return 0;

        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        int[][] dp = new int[m][n];
        dp[0][0] = 1;
        for (int i = 1; i < m; i++) {
            dp[i][0] = dp[i-1][0] & (obstacleGrid[i][0]==1?0:~obstacleGrid[i][0]);
        }
        for (int i = 1; i < n; i++) {
            dp[0][i] = dp[0][i-1] & (obstacleGrid[0][i]==1?0:~obstacleGrid[0][i]);
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = (dp[i-1][j] + dp[i][j-1]) & (obstacleGrid[i][j]==1?0:~obstacleGrid[i][j]);
            }
        }

        return dp[m-1][n-1];
    }

    public static int handle2(int[][] obstacleGrid) {
        if (obstacleGrid[0][0] == 1) return 0;

        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        int[] dp = new int[n];
        dp[0] = 1;
        for (int i = 1; i < n; i++) {
            dp[i] = dp[i-1] & (obstacleGrid[0][i]==1?0:~obstacleGrid[0][i]);
        }
        for (int i = 1; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (j == 0) dp[j] = dp[j] & (obstacleGrid[i][j]==1?0:~obstacleGrid[i][j]);
                else {
                    dp[j] = (dp[j] + dp[j-1]) & (obstacleGrid[i][j]==1?0:~obstacleGrid[i][j]);
                }
            }
        }

        return dp[n-1];
    }
}
